"""
https://leetcode.cn/problems/minimum-path-sum/description/

64. 最小路径和
已解答
中等
相关标签
相关企业
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

"""
from typing import List


class Solution:
    """
    典型的二维矩阵动态规划
    dp的每个元素，表示从左上角到当前元素，最小的数字总和
    dp[0][?]=dp[?][0]=0
    dp[row+1][col+1]=max(dp[row+1][col],dp[row][col+1])+grid[row][col]

    代码思路已经是最优解了，部分细节可以优化
    """

    def minPathSum(self, grid: List[List[int]]) -> int:
        height=len(grid)
        width=len(grid[0])
        dp=[[0]*width for _ in range(height)]
        for (row,rowArr) in enumerate(grid):
            for (col,cell) in enumerate(rowArr):
                if row==0: 
                    if col==0:
                        dp[row][col]=cell
                    else:
                        dp[row][col]=dp[row][col-1]+cell   
                else:
                    if col==0:
                        dp[row][col]=dp[row-1][col]+cell
                    else:
                        dp[row][col]=min(dp[row-1][col],dp[row][col-1])+cell

        return dp[-1][-1]
    
if __name__=='__main__':
    grid = [[1,2,3],[4,5,6]]

    sol=Solution()
    res=sol.minPathSum(grid)
    print(res)